package union_find_Algorithm.leetcode;

/**
 * leetcode上200题
 *
 * 1. 问题描述
 *      给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 *      岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 *      此外，你可以假设该网格的四条边均被水包围。
 *
 * 2. 算法分析
 *     并查集实现
 *
 * 3. 代码实现
 *
 */
// 定义并查集结构
class UnionFind{
    char[][] grid; // 岛屿数组
    int row;
    int col;
    int maxsize;
    int[] root;
    int count;

    public UnionFind(char[][] grid) {
        row = grid.length;
        col = grid[0].length;
        maxsize = row * col;
        root = new int[maxsize];
        count = row * col;
        for(int i = 0; i < maxsize; i++) {
            root[i] = i;
        }
    }

    public int find(int x) {
        if(root[x] == x) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    public void union(int x,int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX != rootY) {
            root[rootY] = rootX;
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}


@SuppressWarnings("all")
public class 最大岛屿问题 {
    public static void main(String[] args) {
        System.out.println('1' + 0);
    }

    public static int numIslands(char[][] grid) {
        int waters = 0;
        UnionFind uf = new UnionFind(grid);
        int row = grid.length;
        int col = grid[0].length;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == '0') {
                    waters++;
                }
                else {
                    // 当前为陆地
                    // 判断以当前位置为中心的四方向
                    if(i - 1 >= 0 && i < row && grid[i-1][j] == '1') {
                        // 判断上 (i-1,j) 二维数组中的索引位置，转化到一维数组的索引位置
                        uf.union(col * (i - 1) + j,col * i + j);
                    }
                    if(i >= 0 && i + 1 < row && grid[i+1][j] == '1') {
                        // 判断下 (i+1,j)
                        uf.union(col * (i + 1) + j, col * i + j);
                    }
                    if(j - 1 >= 0 && j < col && grid[i][j-1] == '1') {
                        // 判断左 (i,j-1)
                        uf.union(col * i + j - 1, col * i + j);
                    }
                    if(j >= 0 && j + 1 < col && grid[i][j+1] == '1') {
                        //  判断右 (i,j+1)
                        uf.union(col * i + j + 1, col * i + j);
                    }
                }
            }
        }
        return uf.getCount() - waters;
    }
}
